\chapter{Further study on simple auctions}
In this chapter, we make some further studies on simple auctions described in the previous chapter. It is conjectured that the lower bound of separate auctions revenue is just $0.78$ fraction of optimal auction revenue. If this is so, we can conclude that for two one-dimensional distribution $F_1$ and $F_2$ where $REV(F_1) = REV(F_2) = 1$, then $REV(F_1 \times F_2) \leq REV(ER \times ER)$. Although it has not be find out whether this conjecture stands, the idea it brings to us is novel: in this way we can make some study on the monotonicity of simple auctions.
\section{Monotonicity}
In this part we introduce a definition called stochastically dominate:

Let $X$ and $Y$ be one-dimensional random variables. If $P(X \geq p) \leq P(Y \geq p)$ for every $p$, then we say $Y$ stochastically dominates $X$. We can see from theorem xxx that $REV(X) \leq REV(Y)$ in this case.
\subsection{Monotonicity for one good}
When in one good case, incentive compatibility indicate that a bidder with a higher valuation pays no less than a bidder with a lower valuation. See the theorem below for details:
\begin{thm}
If a one-dimensional $X$ is stochastically dominated by a one-dimensional $Y$
then $REV(X) \leq REV(Y)$
\end{thm}
\begin{proof}
$REV(X) \leq \sup_p p\cdot P(X\geq p) \leq \sup_p p\cdot P(Y \leq p) = REV(Y)$ 
\end{proof}
\subsection{Nonmonotonicity for multiple goods --- correlated example}
Here we provide an example on two goods which distribution correlates, where the monotonicity does not hold.
\begin{exg}\label{eg1}
For every $0 \leq \alpha \leq \frac{1}{4}$, let $F_\alpha$ be the following distribution on $\mathbb{R}^2$
\begin{equation}
F_\alpha = \left\{ \begin{array}{ll}
(1,1) & \textrm{with probability $\frac{1}{4}$}\\
(1,2) & \textrm{with probability $\frac{1}{4} - \alpha$}\\
(2,2) & \textrm{with probability $\alpha$}\\
(2,3) & \textrm{with probability $\frac{1}{2}$}
\end{array} \right.
\end{equation}
Under this distribution, we can prove that $\forall 0\leq \alpha \leq \frac{1}{12}$
\begin{equation}
REV(F_\alpha) = 11/4 - \alpha
\end{equation}
which indicates that the Revenue decrease with $\alpha$. Furthermore, for any $\alpha > \alpha'$, $F_\alpha$ stochastically dominates $F_{\alpha'}$. This shows that the monotonicity does not hold in this case.
\end{exg}
\begin{proof}
Consider the following inequalities based on IC and IR restriction:
\begin{center}
\begin{tabular}{l|l}
$q^{11}_1 + q^{11}_2 - s^{11} \geq 0$ & $1$\\
$q^{12}_1 + 2q^{12}_2 - s^{12} \geq q^{11}_1 + 2q^{11}_2 - s^{11}$ & $\frac{1}{2}$\\
$2q^{22}_1 + 2q^{22}_2 - s^{22} \geq 2q^{11}_1 + 2q^{11}_2 - s^{11}$ & $3\alpha$\\
$2q^{23}_1 + 3q^{23}_2 - s^{23} \geq 2q^{11}_1 + 3q^{11}_2 - s^{11}$ & $\frac{1}{4} - 3\alpha$\\
$2q^{23}_1 + 3q^{23}_2 - s^{23} \geq 2q^{12}_1 + 3q^{12}_2 - s^{12}$ & $\frac{1}{4} + 3\alpha$\\
$2q^{23}_1 + 3q^{23}_2 - s^{23} \geq 2q^{22}_1 + 3q^{22}_2 - s^{22}$ & $2\alpha$
\end{tabular}
\end{center}
For the inequalities, multiplier the coefficient on the right side and  add them together, we can get:
\begin{equation}
\begin{aligned}
-(\frac{3}{4} - 3\alpha)q{11}_2 - 2\alpha q^{12}_1 + (\frac{1}{4} - 3\alpha) q^{12}_2 + 2\alpha q^{22}_1 + q^{23}_1 + \frac{3}{2}q^{23}_2 \\ \geq \frac{1}{4}s^{11} + (\frac{1}{4}- \alpha)s^{12} + \alpha s^{22} + \frac{1}{2}s^{23}
\end{aligned}
\end{equation}
The right hand side is exactly the expected revenue for $F_\alpha$. For the left hand side, since allocations are all in interval $[0,1]$, thus the left hand side is at most $\frac{11}{4} - \alpha$.
To summarize, see Table\ref{tab1} for the mechanism description.
\begin{table}[!h]
\caption{Non-monotonicity example for correlated valuations}\label{tab1}
\centering
\begin{tabular}{|c|c|c|}
\hline
Valuation & \multicolumn{2}{|c|}{Outcome}\\
\hline
$x$ & $q(x)$ & $s(x)$\\
\hline \hline
$(1,1)$ & $(0, 0)$ & $0$\\
\hline
$(2,2)$ & $(1, 0)$ & $1$\\
\hline
$(1,2)$ & $(0, 1)$ & $2$\\
\hline
$(2,3)$ & $(1, 1)$ & $4$\\
\hline
\end{tabular}
\end{table}
\end{proof}
\subsection{Nonmonotonicity for multiple goods --- independent example}
Here we provide an example on two goods which distribution are independent and identical, where the monotonicity does not hold.
\begin{exg}\label{eg2}
Let $F_1$ and $F_2$ be the following one-dimensional distributions:
\begin{equation}
F_1 = \left\{ \begin{array}{ll}
10 & \textrm{with probability $\frac{4}{15}$}\\
46 & \textrm{with probability $\frac{1}{90}$}\\
47 & \textrm{with probability $\frac{1}{3}$}\\
80 & \textrm{with probability $\frac{7}{30}$}\\
100 & \textrm{with probability $\frac{7}{45}$}
\end{array} \right.
F_2 = \left\{ \begin{array}{ll}
10 & \textrm{with probability $\frac{2399}{9000}$}\\
13 & \textrm{with probability $\frac{1}{9000}$}\\
46 & \textrm{with probability $\frac{1}{90}$}\\
47 & \textrm{with probability $\frac{1}{3}$}\\
80 & \textrm{with probability $\frac{7}{30}$}\\
100 & \textrm{with probability $\frac{7}{45}$}
\end{array} \right.
\end{equation}
We can see that $F_2$ stochastically dominates $F_1$, which implies that $F_2 \times F_2$ stochastically dominates $F_1 \times F_1$, but $REV(F_1 \times F_1) > REV(F_2 \times F_2)$
\end{exg}
\begin{proof}
The method is the same as the previous one, building up inequalities based on IC and IR restriction. For simplicity here we only list the unique optimal mechanism for $F_1 \times F_1$ and $F_2 \times F_2$ in Table\ref{tab2}.
\begin{table}[!h]
\caption{Non-monotonicity example for independent valuations}\label{tab2}
\centering
\begin{tabular}{|c|c|c|}
\hline
Valuation & \multicolumn{2}{|c|}{Outcome}\\
\hline
$x$ & $q(x)$ & $s(x)$\\
\hline \hline
$(10,10),(10,13),(13,10),(13,13),$& & \\
$(10,46),(46,10),(13,46),(46,13),(46,46),$ &$0$ & $(0, 0)$\\
$(13,47),(47,13),(10,47),(47,10)$ &  & \\
\hline
$(46,47)$ & $(\frac{32}{1187}, \frac{384}{13057})$ & $\frac{34240}{13057} \approx 2.6$\\
\hline
$(47,46)$ & $(\frac{384}{13057}, \frac{32}{1187})$ & $\frac{34240}{13057} \approx 2.6$\\
\hline
$(47,47)$ & $(\frac{35}{1187}, \frac{35}{1187})$ & $\frac{3258}{1187} \approx 2.7$\\
\hline
$(13,80)$ & $(\frac{32}{1187}, \frac{5647}{5935})$ & $\frac{90672}{1187} \approx 76.4$\\
\hline
$(80,13)$ & $(\frac{5647}{5935}, \frac{32}{1187})$ & $\frac{90672}{1187} \approx 76.4$\\
\hline
$(46,80)$ & $(\frac{35}{1187}, \frac{5647}{5935})$ & $\frac{90810}{1187} \approx 76.5$\\
\hline
$(80,46)$ & $(\frac{5647}{5935}, \frac{35}{1187})$ & $\frac{90810}{1187} \approx 76.5$\\
\hline
$(10,80),(10,100),(13,100)$ & $(0, 1)$ & $80$\\
\hline
$(80,10),(100,10),(100,13)$ & $(1, 1)$ & $80$\\
\hline
$(46,100),(100,46),
(47,80),(80,47),$& &\\
$(47,100),(100,47),(80,80),(80,100),$ &$(1, 1)$ & $126$\\
$(100,80),(100,100)$ & & \\ 
\hline
\end{tabular}
\end{table}
Then we can calculate the revenue for the two distributions:
\begin{equation}
REV(F_1 \times F_1) = \frac{408189937}{5875650} \approx 69.47145
REV(F_2 \times F_2) = \frac{30614162731}{440673750} \approx 69.47126 
\end{equation}
\end{proof}
\section{Lottery mechanism}
For the case that selling a single object, \cite{myerson1981optimal} told us the deterministic mechanisms receives the optimal revenue. This is not so in multi item case, but instead lottery mechanisms receives the optimal revenue. In this section we provide some examples to show this by calculate some optimal auction mechanism when given certain distribution function.
\subsection{correlated example}
\begin{exg}\label{eg3}
Let $F$ be the following two-dimensional probability distribution:
\begin{equation}
F_\alpha = \left\{ \begin{array}{ll}
(1,0) & \textrm{with probability $\frac{1}{3}$}\\
(0,2) & \textrm{with probability $\frac{1}{3}$}\\
(3,3) & \textrm{with probability $\frac{1}{3}$}
\end{array} \right.
\end{equation}
Then the unique revenue-maximizing IC and IR mechanism for $F$ is as following Table\ref{tab3} indicates:
\begin{table}[!h]
\caption{Lottery mechanism is optimal when correlated valuation occurs}\label{tab3}
\centering
\begin{tabular}{|c|c|c|}
\hline
Valuation & \multicolumn{2}{|c|}{Outcome}\\
\hline
$x$ & $q(x)$ & $s(x)$\\
\hline \hline
$(1,0)$ & $(\frac{1}{2}, 0)$ & $\frac{1}{2}$\\
\hline
$(0,2)$ & $(0, 1)$ & $2$\\
\hline
$(3,3)$ & $(1, 1)$ & $5$\\
\hline
\end{tabular}
\end{table}
\end{exg}
\begin{proof}
Let $<(\alpha_1, \beta_1; \sigma_1)>,<(\alpha_2, \beta_2; \sigma_2)>$, and $<(\alpha_3, \beta_3; \sigma_3)>$ be the outcome $<(q_1(x), q_2(x); s(x))>$ at $x = (1,0),(0,2)$ and $(3,3)$, respectively. The objective function is $S:=\sigma_1 + \sigma_2 + \sigma_3$, which is $3$ times the revenue. Consider the relaxed problem of maximizing $S$ subject only to the individual rationality constraints at $(1,0)$ and $(0,2)$, and to the two incentive compatibility constrain at $(3,3)$:
\begin{equation}
\begin{aligned}
\alpha_1 - \sigma_1 &\geq 0\\
2\beta_2 - \sigma_2 &\geq 0\\
3\alpha_3 + 3\beta_3 - \sigma_3 &\geq 3\alpha_1 + 3\beta_1 - \sigma_1\\
3\alpha_3 + 3\beta_3 - \sigma_3 &\geq 3\alpha_2 + 3\beta_2 - \sigma_2
\end{aligned}
\end{equation}
rewrite these inequalities we get:
\begin{equation}
\begin{aligned}
\alpha_1 &\geq \sigma_1 \geq \sigma_3 + \alpha_1 + 3\beta_1-3\alpha_3 - 3\beta_3\\
2\beta_2 &\geq \sigma_2 \geq \sigma_3 + 3\alpha_2 + 3\beta_2 -3\alpha_3 - 3\beta_3
\end{aligned}
\end{equation}
Thus, to maximize $S$, we should take $\sigma_1 = \alpha_1$ and $\sigma_2 = 2\beta_2$. In this way, for $\sigma_3$, we have:
\begin{equation}
\begin{aligned}
\sigma_3 &\leq 3\alpha_3 + 3\beta_3 - 2\alpha_1 - 3\beta_1\\
\sigma_3 &\leq 3\alpha_3 + 3\beta_3 - 3\alpha_2 - \beta_2
\end{aligned}
\end{equation}
Then we should take $\alpha_3 = \beta_3 = 1$, $\beta_1 = \alpha_2 = 0$, and $\sigma_3 = \min\{6-2\alpha_1, 6-\beta_2\}$. Substitute it into $S$, we have $S = \min\{2\beta_2 - \alpha_1, \beta_2 + \alpha_1\} + 6$. Since $S$ increases when $\beta_2$ increase, we can set $\beta_2 = 1$, and $S = \min\{2 - \alpha_1, 1 + \alpha_1\} + 6$, which is maximized at $\alpha = \frac{1}{2}$.
\end{proof}
\subsection{independent example}
\begin{exg}\label{eg4}
Let $F$ be the following one-dimensional probability distribution
\begin{equation}
F_\alpha = \left\{ \begin{array}{ll}
1 & \textrm{with probability $\frac{1}{6}$}\\
2 & \textrm{with probability $\frac{1}{3}$}\\
4 & \textrm{with probability $\frac{1}{2}$}
\end{array} \right.
\end{equation}
Then the unique revenue-maximizing IC and IR mechanism for $\mathcal{F} := F \times F$ is as following Table\ref{tab4} indicates:
\begin{table}[!h]
\caption{Lottery mechanism is optimal when correlated valuation occurs}\label{tab4}
\centering
\begin{tabular}{|c|c|c|}
\hline
Valuation & \multicolumn{2}{|c|}{Outcome}\\
\hline
$x$ & $q(x)$ & $s(x)$\\
\hline \hline
$(1,1)$ & $(0, 0)$ & $0$\\
\hline
$(2,1)$ & $(\frac{1}{2}, 0)$ & $1$\\
\hline
$(1,2)$ & $(0, \frac{1}{2})$ & $1$\\
\hline
$(1,4),(4,1),(2,2),(2,4),(4,2),(4,4)$ & $(1, 1)$ & $4$\\
\hline
\end{tabular}
\end{table}
\end{exg}
\begin{proof}
First, the revenue from the above mechanism is $\frac{61}{18}$, which can be easily computed.
Second, take the following inequalities, which is a combination of individual rationality and incentive compatibility constraints.
\begin{table}
\centering
\begin{tabular}{l|l}
$q^{11}_1 + q^{11}_2 - s^{11} \geq 0$ & $3$\\
$q^{12}_1 + 2q^{12}_2 - s^{12} \geq 0$ & $8$\\
$2q^{21}_1 + q^{21}_2 - s^{21} \geq 0$ & $8$\\
$2q^{22}_1 + 2q^{22}_2 - s^{22} \geq 0$ & $17$\\
$q^{12}_1 + 2q^{12}_2 - s^{12} \geq q^{11}_1 + 2q^{11}_2 - s^{11}$ & $1$\\
$2q^{21}_1 + q^{21}_2 - s^{21} \geq 2q^{11}_1 + q^{11}_2 - s^{11}$ & $1$\\
$2q^{22}_1 + 2q^{22}_2 - s^{22} \geq 2q^{12}_1 + 2q^{12}_2 - s^{12}$ & $3$\\
$2q^{22}_1 + 2q^{22}_2 - s^{22} \geq 2q^{21}_1 + 2q^{21}_2 - s^{21}$ & $3$\\
$q^{14}_1 + 4q^{14}_2 - s^{14} \geq q^{12}_1 + 4q^{12}_2 - s^{12}$ & $3$\\
$4q^{41}_1 + q^{41}_2 - s^{41} \geq 4q^{21}_1 + q^{21}_2 - s^{21}$ & $3$\\
$2q^{22}_1 + 2q^{22}_2 - s^{22} \geq 2q^{14}_1 + 2q^{14}_2 - s^{14}$ & $1$\\
$2q^{22}_1 + 2q^{22}_2 - s^{22} \geq 2q^{41}_1 + 2q^{41}_2 - s^{41}$ & $1$\\
$2q^{24}_1 + 4q^{24}_2 - s^{24} \geq 2q^{22}_1 + 4q^{22}_2 - s^{22}$ & $8$\\
$4q^{42}_1 + 2q^{42}_2 - s^{42} \geq 4q^{22}_1 + 2q^{22}_2 - s^{22}$ & $8$\\
$4q^{44}_1 + 4q^{44}_2 - s^{44} \geq 4q^{24}_1 + 4q^{24}_2 - s^{24}$ & $2$\\
$4q^{44}_1 + 4q^{44}_2 - s^{44} \geq 4q^{42}_1 + 4q^{42}_2 - s^{42}$ & $2$\\
\end{tabular}
\end{table}
Multiplying each inequality by the weight on the right and adding up yields:
\begin{equation}
\begin{aligned}
s^{11} + 3 s^{12} + 3 s^{21} + 9 s^{22} + 2 s^{14} + 2 s^{41} + 6 s^{24} + 6 s^{42} + 4 s^{44} \\ \leq 2 q^{22}_1 + q^{14}_1 + 10 q^{41}_1 + 8 q^{24}_1 + 24 q^{42}_1 + 16 q^{44}_1\\ + 2 q^{22}_2 + 10 q^{14}_2 + q^{41}_2 + 24 q^{24}_2 + 8 q^{42}_2 + 16 q^{44}_2
\end{aligned}
\end{equation}
The left hand side is precisely 36 times the expected revenue of the seller for the distribution $\mathcal{F} = F \times F$, and the right hand side is bounded above by $122$. Therefore $REV(\mathcal{F}) = \frac{61}{18}$ 
\end{proof}
\section{Summary of this chapter}
In this chapter, we made further studies on simple auction mechanisms, studying the monotonicity in various kinds of situations. It seems that this property only holds when there is only a single object for sell.
